package algorithm.数据量猜解法;

public class MoneyProblem {

    public static long process(int[] d, int[] p, int index, int ability){
         if(index == d.length)
             return 0;

         if(ability < d[index])
             return p[index] + process(d, p, index + 1, ability + d[index]);
         else
             return Math.min(p[index] + process(d, p, index + 1, ability + d[index]),
                     process(d, p, index + 1, ability));
    }


    //*** 从0....index号怪兽，花的钱，必须严格==money ***

    // 如果通过不了，返回-1
    // 如果可以通过，返回能通过情况下的最大能力值
    public static long process2(int[] d, int[] p, int index, int money){
        if(index == 0)
            return money == p[0] ? d[0] : -1;


        long ability1 = process2(d, p, index - 1, money);
        if(ability1 != -1 && ability1 < d[index])
            ability1 = -1;

        long ability2 = process2(d, p, index - 1, money - p[index]);
        if(ability2 != -1)
            ability2 += d[index];

        return Math.max(ability1, ability2);
    }

    public static int minMoney2(int[] d, int[] p) {
        int allMoney = 0;
        for (int i = 0; i < p.length; i++) {
            allMoney += p[i];
        }
        int N = d.length;
        for (int money = 0; money < allMoney; money++) {
            if (process2(d, p, N - 1, money) != -1) {
                return money;
            }
        }
        return allMoney;
    }

    public static long function(int[] d, int[] p){
       int length = d.length;
       int totalMoney = 0;
        for (int i = 0; i < length; i++) {
            totalMoney += p[i];
        }

        int[][] dp = new int[length][totalMoney + 1];

        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j <= totalMoney; j++) {
                dp[i][j] = -1;
            }
        }
        // 经过0～i的怪兽，花钱数一定为p[0]，达到武力值d[0]的地步。其他第0行的状态一律是无效的
        dp[0][p[0]] = d[0];

        for (int i = 1; i < length; i++) {
            for (int j = 0; j <= totalMoney; j++) {
                int tmp1 = dp[i - 1][j];
                if(dp[i - 1][j] != -1 && d[i] > dp[i - 1][j])
                    tmp1 = -1;
                int tmp2 = j - p[i] >= 0 ? dp[i - 1][j - p[i]] : -1;
                if(tmp2!= -1)
                    tmp2 += d[i];
                dp[i][j] = Math.max(tmp2, tmp1);
            }
        }

        for (int i = 0; i < totalMoney; i++) {
            if(dp[length - 1][i] != -1){
                return i;
            }
        }
        return totalMoney;

    }

    public static int[][] generateTwoRandomArray(int len, int value) {
        int size = (int) (Math.random() * len) + 1;
        int[][] arrs = new int[2][size];
        for (int i = 0; i < size; i++) {
            arrs[0][i] = (int) (Math.random() * value) + 1;
            arrs[1][i] = (int) (Math.random() * value) + 1;
        }
        return arrs;
    }


    public static void main(String[] args) {
        int len = 10;
        int value = 20;
        int testTimes = 10000;
        for (int i = 0; i < testTimes; i++) {
            int[][] arrs = generateTwoRandomArray(len, value);
            int[] d = arrs[0];
            int[] p = arrs[1];
            long ans1 = process(d, p, 0, 0);
            long ans2 = minMoney2(d, p);
            long ans3 = function(d, p);

            if (ans1 != ans2 || ans1 != ans3) {
                System.out.println("oops!");
            }
        }

    }


}
